#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: brother.py 
@version:
@time: 2024/01/27 

题目说明二叉树中节点值是唯一的，因此要判断两个节点是否为堂兄弟节点，首先，要搜索到这两个节点

什么条件下两个节点称为堂兄弟节点呢？

1. 两个节点处于同一深度
2. 两个节点的父节点不相同

该问题适合采用广度优先搜索算法并借助队列逐层搜索，一旦搜索到待判断的节点，就将该节点的深度保存到一个字典以供比较。


为了比较父节点，每个节点入队时，将其深度与父节点均入队以供比较
"""
from collections import deque


def brother(root, this_node1, this_node2):
    if not root:
        return False
    # 深度，节点，父节点
    queue = deque([(1, root, None)])
    node1_parent = node2_parent = None
    depth_dict = {}
    while queue:
        depth, node, parent = queue.popleft()
        if node.val == this_node1:
            depth_dict['node1'] = depth
            node1_parent = parent
        if node.val == this_node2:
            depth_dict['node2'] = depth
            node2_parent = parent
        if node.left:
            queue.append((depth + 1, node.left, node))
        if node.right:
            queue.append((depth + 1, node.right, node))
        if node1_parent and node2_parent:
            break
    print(depth_dict)
    print(node1_parent)
    print(node2_parent)
    return depth_dict['node1'] == depth_dict['node2'] and node1_parent != node2_parent


class TreeNode:
    def __init__(self, root):
        self.val = root
        self.left = None
        self.right = None


"""
        5
       / \
      4   3
      \   /
      2   1
"""
Tnode1 = TreeNode(1)
Tnode2 = TreeNode(2)
Tnode3 = TreeNode(3)
Tnode4 = TreeNode(4)
Tnode5 = TreeNode(5)

Tnode5.left = Tnode4
Tnode5.right = Tnode3
Tnode4.right = Tnode2
Tnode3.left = Tnode1

find_node1 = 4
find_node2 = 3

print(brother(Tnode5, find_node1, find_node2))
